BUILDING A FINITELY GENERATING SYSTEM IN A GROUP OF KALMAR-ELEMENTARY PERMUTATIONS

Marchenkov Sergey Serafimovich, Doctor of physical and mathematical sciences, professor, sub-departmentof mathematical cybernetics, Lomonosov Moscow State University (1 Leninskie gory street, Moscow, Russia), ssmarchen@yandex.ru

519.716

10.21685/2072-3040-2016-2-2

Background. Over 30 years ago, at the interface of the theory of recursive functions and the theory of groups there was formulated a problem of finite generation of some large groups of recursive permutations, associated with classes of the Grzegorczyk hierarchy. This problem was successfully solved by S. A. Volkov in 2008. S. A. Volkov’s solution was technically quite complicated and used a series of facts, the solution of which required considerable efforts of many mathematicians. Despite the fact that stages of proving were separately published, so far there has been no independent description that doesn’t require addressing other statements and sources. The aim of this work is to describe all stages of obtainment of S.A. Volkov’s theorem by the example of a group of Kalmar-elementary permutations. Besides, the study is also aimed at explicitely defining all ermutations (total amount – 22) that generate the group under consideration. This creates preconditions for analyzing number-theoretic, algebraic and recursivetheoretic properties of permutations from a sufficiently broad and representative group of Kalmar-elementary permutations.
Materials and methods. In the study the author used recursive-theoretic, algebraic and combinatorial methods.
Results and conclusions. The author described (without proving) three stages of S.A. Volkov’s theorem obtainment. All side results, occurring while using the results of different authors, were deleted. For the first stage (superposition construction of finite bases in the K function Kalmar-elementary class) the researcher considered the whole path – from A. Grzegorczyk’s formaulation of the problem in 1953 till obtainment of the “final” result in 2006. The second stage (superposition constructionof finite bases in the class of all one-place functions from K) was described with proving, prepared specifically for the present work. The third stage (construction of the finite generating system in the GK group of all permutation from the K class) generally follows the original work of S.A. Volkov.

Kalmar-elementary permutations, finitely presented permutation group.

1. Grzegorczyk A. Rozprawy Matematiczne [Mathematical apparatus]. 1953, vol. 4, pp. 1–44.
2. Marchenkov S. S. Matematicheskie voprosy kibernetiki [Mathematical problems of cybernetics]. 1991, iss. 3, pp. 115–139.
3. Volkov S. A. Diskretnaya matematika [Discrete mathematics]. 2008, vol. 20, no. 4, pp. 61–78.
4. Marchenkov S. S. Predstavlenie funktsiy superpozitsiyami [Superposition representation of functions]. Moscow: Komkniga, 2010, 189 p.
5. Kalmar L. Matematikai és fizikai lapok [Mathematical and physical journal]. 1943, vol. 50, pp. 1–23.
6. Marchenkov S. S. Elementarnye rekursivnye funktsii [Elementary recursive functions]. Moscow: MTsNMO, 2003, 112 p.
7. Rödding D. Zeitsch. math. Logik u. Grundlagen Math. [Journal of mathematical logic and mathematical principles]. 1964, vol. 10, no. 4, pp. 315–330.
8. Parsons Ch. Zeitschr. math. Logik u. Grundlagen Math. [Journal of mathematical logic and mathematical principles]. 1968, vol. 14, no. 4, pp. 357–376.
9. Kozmidiadi V. A., Marchenkov S. S. Problemy kibernetiki [Problems of cybernetics]. 1969,iss.21,pp.127–158.
10. Marchenkov S. S. Matematicheskie zametki [Mathematical notes]. 1969, vol. 5, no. 5, pp. 561–568.
11. Marchenkov S. S. Mathematica Balkanica [Balcan mathematics]. 1972, vol. 2, pp. 124–142.
12. Matiyasevich Yu. V. Izvestiya AN SSSR. Ser. Matem. [Proceedings of AS USSR. Mathematical series]. 1971, vol. 35, no. 1, pp. 3–30.
13. Marchenkov S. S. Matematicheskie zametki [Mathematical notes]. 1980, vol. 27, no. 3, pp. 321–332.
14. Marchenkov S. S. Vsesoyuznaya konferentsiya po prikladnoy logike [All-USSR conference on applied logic]. Novosibirsk, 1985, pp. 139–141.
15. Marchenkov S. S. Combinatorics and Graph Theory. Banach Center Publications.1989,vol.25,pp.119–126.
16. Matiyasevich Yu. V. Zapiski nauchnykh seminarov Leningradskogo otdeleniya matem. in-ta AN SSSR [Proceedings of scientific seminars of the Leningrad branch of the Institute of Mathematics of AS USSR]. 1974, vol. 40, pp. 77–93.
17. Matiyasevich Yu. V. Zapiski nauchnykh seminarov Leningradskogo otdeleniya matem. in-ta AN SSSR [Proceedings of scientific seminars of the Leningrad branch of the Institute of Mathematics of AS USSR]. 1976, vol. 60, pp. 75–92.
18. Mazzanti S. Math. Logic Quarterly. 2002, vol. 48, pp. 93–104.
19. Marchenkov S. S. Diskretnyy analiz i issledovanie operatsiy. Ser. 1. [Discrete analysis and research of operations. Series 1]. 2006, vol. 13, no. 4, pp. 33–48.
20. Marchenkov S. S. Elementarnye arifmeticheskie funktsii [Elementary arithmetic functions]. Moscow: Librokom, 2009, 47 p.
21. Mal'tsev A. I. Algebra i logika [Algebra and logic]. 1966, vol. 5, no. 2, pp. 5–24.
22. Mal'tsev A. I. Iterativnye algebry Posta [Post iterative algebras]. Novosibirsk: Izd-vo Novosib. gos. un-ta, 1976, 100 p.
23. Mal'tsev A. I. Algoritmy i rekursivnye funktsii[Algorithms and recursive functions].Moscow:Nauka,1986,366p.